n=10000;
d=[756,214,223,686,31,864,369,733,235,623,150,944,691,961,63,753,621,913,534,787,771,344,669,505,882,483,889,190,560,742,82,715,946,143,866,243,594,621,759,788,403,690,234,420,895,440,335,883,208,539,37,700,591,59,478,45,531,923,644,857,825,946,537,865,466,115,147,236,871,862,163,212,393,489,914,933,302,739,568,916,819,426,978,604,963,60,397,25,18,615,516,177,22,65,884,907,829,501,953,185,406,479,349,953,314,167,475,690,460,917,283,364,843,187,565,831,607,548,169,869,388,261,204,616,542,831,299,113,599,815,929,540,397,49,322,814,53,294,739,591,344,65,202,876,548,867,700,829,125,711,729,936,311,267,804,911,954,608,694,675,59,77,261,722,881,919,315,662,978,442,391,571,661,709,895,300,615,968,856,516,590,890,802,517,40,335,703,665,636,465,438,748,970,111,395,552,389,697,802,528,957,933,933,520,417,66,904,980,941,365,964,81,364,43,404,610,525,934,808,924,794,316,487,48,853,623,508,50,146,732,129,447,465,678,696,367,380,747,545,653,324,237,228,404,669,760,229,680,164,529,666,888,483,974,972,365,644,855,244,707,682,714,428,764,607,30,110,694,726,794,476,107,316,363,399,275,542,845,385,184,727,421,267,352,412,961,920,871,972,871,404,762,12,305,257,213,92,870,233,328,124,683,659,237,532,509,934,75,380,250,851,316,94,516,559,830,253,822,461,824,872,558,807,975,554,196,745,979,848,666,467,623,353,373,133,804,294,748,107,715,957,176,341,411,778,1000,390,408,644,378,286,859,101,244,216,158,433,141,531,595,694,943,62,937,960,81,492,635,172,874,953,711,497,910,399,987,329,713,560,226,790,653,435,291,996,195,29,115,239,476,209,118,472,180,898,336,687,11,534,333,762,541,854,72,634,174,509,989,33,710,371,48,258,430,76,819,945,804,848,344,762,763,608,921,360,287,898,52,531,574,481,508,227,315,935,919,764,985,69,473,80,735,207,529,849,632,173,128,983,878,441,1000,210,819,872,931,901,463,509,417,877,165,242,375,949,70,139,390,448,63,126,943,355,812,835,97,986,940,396,826,239,134,1000,247,648,883,121,278,720,532,594,575,188,699,949,125,825,779,556,977,570,775,544,923,42,734,130,46,986,487,196,172,461,713,474,766,158,401,99,239,437,89,985,714,218,830,895,876,1,12,777,523,375,943,619,255,467,432,428,533,233,737,584,388,827,73,812,521,801,226,24,357,142,102,711,228,810,479,470,662,312,326,99,871,441,323,546,509,964,155,832,290,457,463,51,530,931,212,289,239,883,519,756,904,580,250,991,336,519,481,336,811,748,746,361,411,618,433,777,0,615,528,322,123,82,449,244,916,755,773,33,666,764,737,697,45,408,870,783,757,804,877,353,306,23,301,181,807,319,964,492,212,334,590,623,267,941,701,221,636,895,413,981,133,959,665,657,542,820,433,777,522,57,115,948,670,372,642,827,161,544,673,641,199,938,356,956,202,57,957,938,886,1000,156,302,150,609,902,594,66,25,424,160,918,554,22,488,316,879,315,332,42,554,662,195,43,676,203,228,678,710,331,999,714,642,57,745,145,419,62,122,748,985,474,43,849,99,539,153,318,435,568,562,226,267,765,848,589,968,417,746,778,704,300,91,140,730,661,379,29,586,913,543,394,537,399,697,673,200,124,634,269,217,150,942,657,945,69,648,749,735,26,840,694,782,470,454,450,894,506,543,219,291,938,113,424,15,603,830,733,223,75,359,136,266,917,627,406,927,753,403,243,296,840,135,210,256,65,886,686,734,255,515,11,722,146,702,827,637,63,151,824,242,948,169,987,124,876,296,872,822,649,762,588,884,61,932,960,49,824,745,398,298,275,888,355,293,693,0,149,189,645,249,55,851,397,265,981,791,768,769,625,346,787,515,302,54,508,392,817,788,334,81,761,802,805,932,496,989,297,224,833,143,421,286,179,919,669,289,136,775,490,792,864,503,914,23,374,178,715,248,314,215,617,162,466,736,749,940,137,8,103,112,79,843,831,37,971,767,252,697,195,893,304,574,538,614,138,241,504,187,817,761,908,954,286,15,182,168,315,576,950,159,498,323,938,785,422,265,608,150,392,219,563,225,337,612,485,705,224,632,67,618,949,810,201,890,748,114,348,773,585,89,83,973,452,329,428,906,490,513,934,22,974,413,437,43,555,19,465,193,942,869,101,244,158,452,540,892,79,826,475,544,872,60,487,457,855,711,49,202,696,346,944,972,806,85,19,790,309,333,332,520,991,294,949,167,174,761,869,515,881,481,532,444,208,260,930,369,843,894,518,99,138,221,797,542,744,673,175,746,145,824,470,170,331,377,125,583,561,255,365,93,283,881,372,198,220,854,134,842,2,189,994,880,911,582,802,983,600,939,998,957,330,279,245,656,970,342,247,685,679,481,669,47,904,786,78,98,627,742,831,190,912,196,208,630,441,336,726,118,903,138,982,818,351,711,95,709,347,842,248,590,516,845,470,498,999,540,60,590,280,220,827,513,739,758,17,578,344,823,377,819,812,47,236,356,34,147,954,349,600,93,186,347,256,741,102,119,33,436,319,171,818,514,231,75,553,912,132,216,566,973,938,483,783,18,603,806,224,825,302,253,448,782,323,744,467,51,809,545,281,693,200,739,752,243,221,731,603,724,630,785,742,683,604,465,913,588,329,768,488,179,1,726,887,122,491,168,246,564,385,410,370,339,715,752,143,350,782,427,425,786,662,427,203,134,350,881,280,13,739,2,628,713,510,305,694,552,540,514,193,400,322,579,174,843,912,1,163,483,331,459,580,36,498,947,156,647,616,631,752,876,198,970,104,775,539,26,796,369,886,778,867,846,543,641,715,262,540,846,410,443,63,709,8,414,369,594,99,612,424,690,501,190,586,254,163,737,158,913,148,752,957,856,218,277,110,560,966,291,248,971,667,495,473,781,465,396,994,65,161,140,272,562,874,657,471,572,357,382,928,719,870,470,917,41,710,678,479,501,637,334,535,716,658,649,922,349,675,971,460,92,914,72,153,820,936,305,457,639,791,651,395,833,473,33,653,922,980,248,866,713,35,739,185,343,400,830,474,1000,585,759,845,263,778,302,177,57,208,24,400,116,148,106,482,434,825,834,893,462,600,667,503,24,19,850,728,712,972,736,569,666,570,528,987,221,908,967,929,530,0,540,66,813,121,26,306,487,172,275,202,794,843,137,82,644,233,214,390,916,448,675,255,870,938,105,480,748,501,343,532,977,683,55,609,320,46,158,667,337,77,324,321,198,695,769,264,778,751,152,663,325,794,445,872,368,227,176,818,388,233,870,488,595,880,731,993,568,573,935,938,746,766,510,630,836,708,437,620,658,817,719,619,842,487,776,874,416,818,609,660,959,946,906,89,913,715,77,762,272,871,418,675,826,657,746,313,434,70,715,166,594,904,851,647,339,322,963,24,334,843,391,588,609,580,301,547,317,944,663,62,640,335,270,565,711,84,360,791,476,630,974,933,825,217,659,375,641,899,396,154,546,123,778,167,698,666,294,625,571,409,618,24,704,802,963,552,996,463,604,387,796,507,91,112,344,861,426,178,17,496,414,379,473,405,665,143,877,264,81,43,778,824,697,167,881,473,927,573,59,396,137,886,269,112,103,882,561,643,468,262,637,99,200,692,143,40,615,609,143,748,770,110,345,688,956,391,458,379,121,682,309,388,311,869,860,462,528,475,853,601,164,487,529,652,756,70,874,370,288,664,748,298,308,334,183,159,283,20,822,963,180,667,733,519,553,396,971,762,680,269,254,621,852,954,211,148,974,321,657,633,82,242,824,819,759,105,99,61,907,810,498,535,648,569,667,102,408,872,22,416,847,276,357,293,491,977,229,126,1,649,54,64,471,460,781,545,65,966,748,895,222,390,749,183,285,974,846,130,896,16,830,338,454,419,61,239,580,521,824,565,425,434,487,323,499,667,202,476,868,557,971,265,940,187,227,610,897,345,195,947,526,840,624,576,864,1000,234,806,258,282,189,329,790,851,248,861,815,120,920,365,149,997,780,387,641,239,187,425,725,825,281,442,361,533,750,714,104,991,408,243,503,534,83,654,185,634,74,863,700,228,539,119,894,916,338,449,294,10,327,467,406,509,426,677,341,517,351,284,560,125,920,563,707,290,841,511,703,677,358,528,164,484,284,994,618,778,853,922,855,92,535,136,69,674,365,136,41,527,438,158,15,589,446,808,508,364,907,536,430,553,243,335,93,322,873,829,76,95,186,881,466,23,703,910,607,336,862,802,583,488,596,773,220,350,760,703,102,856,696,45,221,652,920,542,198,898,999,54,341,969,26,332,422,979,367,669,190,668,797,163,41,839,794,400,250,919,4,564,785,397,527,875,83,589,864,164,147,919,196,676,744,386,826,699,828,4,285,438,60,503,175,188,818,83,328,328,557,277,634,305,984,673,444,377,622,122,490,835,900,969,905,76,671,818,98,823,755,821,997,766,146,322,337,690,774,654,32,818,261,379,943,467,981,768,608,484,867,310,820,406,323,28,332,974,471,162,34,309,919,534,613,926,554,220,240,883,575,542,224,246,364,692,448,85,903,731,636,528,962,640,41,832,864,83,284,159,201,136,587,421,671,645,213,951,560,803,565,503,912,308,348,301,503,518,21,737,522,787,154,684,587,913,736,66,426,510,461,686,692,84,500,276,788,880,678,432,569,284,657,917,597,233,893,778,347,64,929,653,51,489,145,259,891,754,390,663,847,978,417,728,155,443,538,999,923,648,686,159,658,213,983,997,434,598,109,257,730,187,999,288,422,245,532,887,405,690,388,100,194,446,133,567,553,574,329,60,344,675,471,285,68,365,691,111,551,3,270,500,510,279,943,496,112,857,370,174,831,491,4,377,991,755,239,614,357,294,626,614,144,377,465,877,668,715,169,187,625,325,948,944,504,742,678,723,28,440,59,839,833,721,586,730,863,423,692,443,181,278,802,329,146,37,502,239,154,73,317,263,734,482,858,913,273,621,910,601,157,40,984,351,75,283,468,204,340,714,706,378,560,631,700,478,488,696,160,292,209,785,403,640,53,745,291,708,995,346,14,311,394,30,717,543,573,902,512,448,345,714,156,565,164,159,220,31,15,265,637,503,40,265,150,919,692,716,338,921,723,440,528,750,834,542,210,691,891,541,798,546,174,744,336,674,53,17,628,946,577,626,753,6,792,445,768,561,770,970,345,752,66,446,293,521,328,230,988,662,872,796,153,8,568,232,243,738,40,221,600,658,290,503,14,220,783,600,943,638,902,962,624,219,459,114,370,6,522,120,188,348,389,996,551,420,703,875,60,408,235,795,126,372,600,125,698,882,178,785,88,381,899,176,506,895,195,249,354,250,39,509,750,327,714,69,858,918,688,637,456,933,364,600,644,417,280,211,177,80,326,456,584,69,883,420,674,565,687,451,915,70,695,424,518,236,612,34,936,25,961,519,1,780,81,739,681,645,752,798,965,905,351,905,361,497,981,27,982,913,489,388,389,601,233,954,655,971,122,287,564,96,177,539,501,641,70,402,985,27,283,846,20,326,621,847,619,849,487,787,787,899,32,835,219,619,937,340,429,967,947,6,396,43,293,823,5,177,167,92,981,60,618,732,253,979,689,390,437,419,362,488,993,855,798,83,432,594,952,268,355,293,540,931,306,363,933,631,972,746,837,480,605,263,414,760,490,897,112,238,272,480,549,288,652,351,259,895,532,462,327,210,581,872,473,984,370,685,751,336,244,571,224,525,573,956,46,867,831,673,865,557,169,613,179,129,337,275,397,44,739,948,832,741,614,973,713,721,508,633,269,587,763,96,91,375,451,552,70,975,2,746,190,498,493,290,103,521,616,165,179,70,343,217,957,503,893,577,561,190,44,40,211,37,852,585,345,974,39,730,362,184,817,959,451,336,446,500,639,497,601,261,483,120,295,560,620,897,83,513,416,822,422,890,15,613,604,274,87,706,720,647,676,289,984,46,239,499,709,45,267,94,277,509,958,910,122,540,131,169,573,956,645,390,856,801,652,327,81,686,850,186,70,1,712,314,889,952,431,180,278,949,459,553,409,941,985,88,72,738,97,530,17,353,1,147,603,518,344,490,608,275,866,991,792,893,565,978,191,126,196,839,799,319,818,349,118,28,676,18,634,253,349,729,706,335,23,359,218,480,702,349,207,796,241,956,730,814,923,674,4,1000,954,182,90,680,902,612,326,803,163,734,580,747,173,577,101,680,362,368,538,487,816,977,534,812,788,153,257,206,623,722,207,292,318,725,37,369,859,717,280,54,56,997,462,401,11,761,543,26,43,819,703,888,234,202,796,405,961,507,630,947,105,484,970,822,609,236,878,738,102,115,210,556,324,82,550,326,358,642,555,508,371,447,619,868,504,823,740,989,973,95,214,765,981,143,749,886,704,672,901,473,549,844,219,825,115,274,645,759,352,362,760,236,254,432,94,277,34,783,243,774,773,996,891,819,371,792,840,147,10,188,572,293,35,91,804,977,765,327,724,68,699,108,970,124,193,278,715,37,664,618,520,853,56,438,11,703,700,141,957,345,773,176,62,215,466,880,160,621,251,289,735,710,360,791,149,232,278,24,256,44,679,246,580,182,897,503,746,554,15,991,837,574,511,331,128,260,327,205,5,744,477,969,515,613,34,859,457,583,780,361,49,591,179,954,423,730,51,833,988,357,822,17,739,698,427,910,883,834,445,851,488,325,619,409,127,271,991,501,297,72,471,16,219,737,678,551,774,618,406,828,83,128,38,355,859,403,954,610,232,833,288,760,214,11,516,64,442,410,960,824,377,628,448,129,510,484,115,312,935,372,504,123,349,452,388,242,350,151,629,976,814,786,137,995,57,785,462,653,495,953,342,72,700,558,785,221,352,509,771,348,261,809,518,886,800,408,269,599,15,326,703,568,841,432,671,741,590,942,455,814,676,415,247,498,444,321,322,661,546,224,259,600,11,255,381,228,340,462,95,978,88,75,139,341,558,253,769,43,803,570,594,241,349,798,997,656,164,144,708,908,279,586,357,804,780,600,951,749,468,30,524,467,56,225,324,107,895,188,758,329,663,131,976,870,170,396,955,494,401,908,216,83,335,47,325,250,394,105,982,995,390,110,809,968,688,565,255,276,601,118,856,421,251,571,758,973,675,666,588,750,38,431,525,436,723,471,851,738,345,998,478,328,920,681,583,464,907,441,550,347,374,257,83,259,674,336,950,228,586,728,351,223,359,938,139,822,8,307,480,554,847,179,526,483,705,49,863,240,600,909,816,928,842,880,295,497,81,316,903,576,511,884,303,438,667,299,379,311,961,400,211,992,258,69,556,963,615,135,267,865,887,891,667,821,958,368,299,290,168,248,609,856,817,679,97,796,129,947,641,639,19,622,43,7,258,37,581,117,471,534,194,590,137,94,542,691,379,397,534,74,150,607,654,47,365,692,632,321,360,407,324,967,142,722,843,557,377,893,405,582,318,768,57,54,400,65,62,253,244,88,974,860,889,179,243,632,611,757,367,833,618,276,334,945,228,733,1000,698,849,342,31,694,291,655,481,430,725,836,728,195,650,562,25,307,989,898,372,53,289,909,656,798,827,659,981,740,543,825,621,904,508,987,392,780,251,527,927,374,817,436,302,956,43,957,495,359,860,258,601,161,776,168,546,162,251,269,354,340,508,111,953,420,776,891,294,276,110,979,381,904,135,109,12,804,812,67,384,386,248,270,12,40,21,297,69,698,955,785,858,363,564,262,168,775,629,190,596,396,839,484,731,671,682,568,63,816,637,235,827,725,850,778,773,787,687,434,875,536,702,344,958,863,638,102,830,47,186,177,404,483,195,613,303,292,470,285,134,468,138,55,342,825,314,338,893,100,268,190,720,202,639,499,526,31,496,240,712,73,111,917,724,400,766,320,578,892,804,332,423,365,697,119,35,907,215,394,123,302,924,994,778,679,203,805,57,793,251,247,41,730,531,244,225,490,303,118,632,524,880,563,949,351,556,232,236,82,428,857,613,826,134,594,924,977,784,477,960,463,889,964,620,531,630,791,753,719,129,449,382,965,184,848,865,274,72,121,810,640,214,825,459,753,300,244,700,691,272,247,807,773,780,471,156,933,851,580,909,956,182,444,161,222,644,764,610,79,920,774,828,520,908,465,20,916,20,77,451,485,89,140,152,174,112,565,354,349,961,321,925,248,631,951,850,469,606,711,117,365,701,943,916,902,304,662,620,175,357,992,181,440,281,752,162,226,912,982,71,360,550,563,285,812,104,818,528,143,952,129,527,611,566,294,104,167,893,964,789,695,812,128,411,352,136,816,56,32,571,633,434,396,93,697,113,349,63,496,357,754,856,522,444,624,82,688,172,590,639,244,49,836,310,8,52,159,421,736,904,459,734,231,317,615,415,888,919,766,346,181,368,990,982,586,795,936,619,96,741,489,311,894,485,887,689,817,255,705,11,349,755,111,188,737,356,651,427,371,454,772,667,910,645,844,52,140,703,890,136,652,743,965,490,248,450,204,899,543,12,721,205,110,183,471,648,59,532,203,972,47,356,148,1000,536,582,364,898,465,662,585,967,772,379,797,763,812,12,177,783,296,426,566,185,758,460,627,582,733,473,152,146,971,676,238,427,198,424,408,287,1000,289,815,824,110,186,918,982,460,980,798,836,306,395,171,384,139,801,497,241,232,250,568,931,329,117,81,937,304,250,13,928,752,257,664,337,766,695,212,1,799,362,18,616,393,456,765,53,466,548,518,898,993,263,533,967,28,152,985,502,410,152,725,947,900,938,722,420,390,651,237,388,853,79,526,66,978,528,385,766,163,926,140,887,48,125,889,247,829,921,359,509,620,782,427,659,750,855,590,567,202,23,593,437,602,198,436,997,69,387,29,717,671,526,802,755,945,237,811,409,549,804,381,297,219,523,714,687,800,870,12,272,890,207,605,437,83,337,715,710,132,355,81,689,37,623,660,586,26,567,579,813,203,942,902,23,382,195,697,487,550,576,428,574,331,534,382,871,611,472,304,591,481,325,900,885,689,983,757,381,53,343,125,911,671,890,76,555,469,457,797,33,596,86,496,755,620,857,243,499,589,314,199,177,461,673,834,862,735,611,516,650,145,609,116,404,459,141,61,980,796,233,711,899,229,640,227,895,338,366,65,811,298,711,596,104,526,866,818,103,376,111,524,334,95,786,279,459,44,631,666,737,796,236,125,662,349,593,826,17,582,385,174,599,763,381,997,387,408,382,584,235,282,82,660,356,592,918,165,576,205,334,589,493,332,238,40,757,283,282,776,60,132,395,991,460,345,981,673,104,161,533,876,61,603,30,333,478,55,406,803,787,40,243,9,810,148,703,294,640,122,526,306,748,332,150,487,705,630,4,903,527,522,685,163,665,805,186,851,135,456,241,105,841,130,976,939,282,899,951,379,365,650,66,780,842,971,320,647,969,157,776,261,272,332,598,79,187,652,45,700,530,649,14,697,869,19,752,308,29,81,208,695,37,30,483,298,324,15,927,241,358,113,214,99,971,530,584,690,676,319,36,673,993,711,249,261,48,278,641,181,744,636,333,44,783,810,669,811,427,815,396,499,243,889,108,37,894,221,556,685,901,515,636,413,674,0,155,703,618,812,656,315,643,722,661,70,448,61,846,479,949,288,631,305,107,581,360,879,239,681,847,326,722,841,233,17,176,657,705,941,236,360,87,769,271,871,335,469,647,534,807,428,425,900,485,288,952,543,771,175,144,556,799,90,695,275,699,904,795,678,392,984,104,29,838,548,564,263,526,97,23,309,924,388,337,54,239,99,205,9,924,999,959,855,944,116,476,61,407,409,115,101,551,437,93,420,283,223,276,893,503,932,561,412,761,163,99,194,739,250,324,290,253,358,469,81,481,47,310,146,57,889,20,251,831,974,602,592,814,269,231,30,396,694,461,762,253,19,68,777,600,702,50,326,28,831,468,951,798,726,256,115,103,830,270,830,856,10,648,847,834,275,846,699,613,6,52,706,283,519,910,247,113,974,254,397,468,313,523,631,806,548,717,839,878,936,271,416,899,63,141,837,948,201,270,537,633,755,678,628,538,441,378,364,561,461,474,29,554,940,8,408,783,614,846,226,96,155,854,374,743,973,278,773,612,17,470,631,147,58,983,664,728,438,566,769,756,229,237,271,683,566,937,42,680,19,610,549,896,308,659,467,52,394,557,454,872,132,26,57,449,792,370,926,930,539,927,223,258,74,851,544,982,418,350,670,617,906,81,541,73,649,242,836,330,737,95,451,212,710,421,220,939,520,465,388,690,296,442,673,433,275,831,392,238,971,554,686,883,303,66,336,833,664,812,265,315,798,47,602,607,841,83,710,398,594,681,269,233,763,33,527,55,500,106,81,902,681,678,557,519,717,792,306,192,66,188,710,927,264,816,933,734,649,88,421,116,686,507,646,995,246,768,603,675,462,592,66,100,830,759,266,116,5,116,534,716,409,836,690,426,702,790,312,433,765,309,882,309,506,826,602,638,323,952,738,602,952,114,883,506,514,183,354,468,168,515,605,198,693,300,828,145,997,479,391,576,174,577,480,120,279,749,686,737,343,908,85,663,353,872,615,678,235,684,53,279,178,240,573,21,679,80,937,433,683,565,339,42,453,676,335,924,447,125,762,116,733,706,48,360,152,564,366,308,745,69,996,387,505,666,798,395,881,1000,941,895,731,617,24,323,343,64,402,729,885,208,787,95,569,881,477,158,986,873,613,604,35,933,689,482,502,162,35,627,331,245,3,893,163,737,209,254,507,746,113,201,352,151,250,162,556,875,50,352,156,610,864,264,700,900,211,296,289,191,384,917,143,658,961,519,681,330,374,294,424,648,554,31,673,357,172,472,564,819,44,380,111,555,995,68,706,938,177,158,428,727,930,8,557,555,375,361,296,194,4,665,596,130,940,229,322,253,226,956,991,141,556,602,267,244,537,928,67,478,554,355,769,210,556,176,66,701,600,35,23,253,927,706,895,442,193,89,112,487,787,644,761,478,917,900,92,26,527,792,239,664,503,794,719,94,634,896,454,610,270,128,435,248,553,93,727,896,521,735,179,1000,798,267,622,615,831,976,508,440,21,468,352,560,1,975,726,533,808,715,965,865,721,65,144,706,786,313,782,660,986,37,418,563,24,829,557,217,185,577,776,537,552,29,460,626,212,733,937,895,92,23,553,737,616,604,899,514,521,829,740,146,148,903,583,734,377,656,675,874,470,909,603,771,668,661,698,711,241,844,405,365,907,196,609,576,128,523,780,259,932,805,334,500,939,802,534,700,800,471,524,263,542,694,894,429,857,308,572,199,679,383,304,675,850,83,920,518,356,523,443,121,729,816,448,782,964,253,676,44,133,511,590,906,626,189,504,613,614,411,752,240,702,406,25,104,386,228,240,176,319,525,370,355,715,542,314,785,816,407,879,89,564,411,205,457,890,211,99,113,631,521,934,449,636,487,579,244,515,114,773,794,550,171,217,893,624,297,577,569,991,945,258,871,594,238,114,912,580,284,746,476,314,541,733,429,560,214,209,199,315,576,878,675,313,216,877,307,619,385,644,477,100,907,224,873,636,54,159,962,459,771,19,337,225,168,595,531,874,123,218,375,329,802,233,254,899,478,895,866,211,100,730,393,294,211,847,242,997,414,260,929,269,311,58,496,611,201,507,288,335,997,946,777,957,285,876,118,227,125,401,20,390,80,683,440,203,454,980,335,405,893,555,279,303,710,685,773,515,441,600,4,844,685,11,964,770,420,933,612,841,836,381,815,519,463,19,983,540,0,354,970,554,446,224,844,783,307,446,42,181,614,603,230,784,109,455,577,532,988,286,394,479,292,717,345,773,640,213,561,419,102,862,680,529,662,780,568,643,238,128,125,382,900,849,212,644,100,317,282,178,173,488,139,964,264,669,872,925,882,513,676,986,133,25,81,673,106,4,930,196,293,574,99,629,837,234,68,377,4,51,417,817,872,640,776,204,149,965,973,742,58,80,259,959,201,58,107,395,448,882,600,83,797,335,453,86,770,58,604,101,640,247,395,99,926,976,432,48,362,962,431,378,109,934,400,643,624,960,650,452,29,549,105,1000,115,518,693,67,198,418,110,288,912,164,863,63,925,952,548,202,212,296,166,499,430,463,922,247,750,263,187,372,754,674,16,881,545,999,124,953,407,553,933,615,428,411,138,219,656,611,662,928,53,203,988,186,945,600,144,211,330,981,170,260,831,238,164,800,572,463,259,875,558,740,608,630,686,414,931,811,58,908,257,943,232,221,160,919,148,295,702,712,883,269,558,371,322,175,653,104,765,402,389,911,283,612,339,576,285,485,100,994,287,382,409,925,180,546,96,767,964,843,777,651,158,481,506,826,602,356,281,156,223,513,785,957,315,967,470,510,985,826,635,381,503,943,635,543,860,767,159,325,904,261,566,22,352,286,58,476,876,75,414,728,890,144,266,205,493,94,264,859,971,393,394,820,532,993,328,506,102,403,885,662,238,652,820,872,706,859,495,648,244,531,507,497,548,536,523,672,38,574,455,473,350,58,311,620,636,899,326,734,477,497,833,180,140,134,658,936,767,915,579,432,992,139,343,338,399,988,798,299,917,791,692,638,509,458,781,695,356,26,895,650,66,961,987,96,681,983,983,753,677,362,753,521,454,245,474,35,47,213,249,201,812,578,769,905,958,713,271,323,802,172,422,243,9,248,792,903,674,28,96,854,246,143,466,97,807,565,782,260,158,570,653,175,532,328,171,488,57,635,231,370,830,626,422,422,907,706,977,96,554,699,407,45,335,324,756,77,446,902,223,919,599,49,185,625,9,655,718,42,645,620,899,917,205,191,222,161,825,255,845,179,497,701,920,706,63,530,801,290,24,468,528,39,532,419,918,882,553,510,982,851,46,808,173,264,921,381,856,760,67,416,860,109,976,484,954,633,174,901,212,222,526,846,168,788,329,183,564,632,189,915,3,772,361,990,256,528,328,69,893,673,800,491,205,133,355,120,636,659,521,914,769,128,230,152,514,402,704,336,322,496,961,926,563,524,8,619,937,671,795,139,995,442,580,467,683,44,948,796,203,709,492,51,923,119,630,349,986,531,254,18,848,12,401,778,146,399,581,981,667,233,791,250,761,979,259,814,911,745,621,152,630,94,929,227,165,515,726,97,245,367,42,944,964,959,208,71,906,217,196,422,411,397,596,243,704,985,820,30,136,472,740,426,619,842,375,388,920,906,272,401,954,775,371,261,639,742,468,248,521,492,596,665,524,29,401,324,82,845,11,632,708,785,533,669,801,526,452,862,732,621,942,102,190,457,619,978,640,7,679,779,183,82,446,925,631,768,848,244,196,219,28,73,241,276,970,964,757,214,282,199,56,478,62,797,261,352,9,175,69,368,699,618,501,462,743,179,418,749,73,430,723,155,371,791,949,836,893,61,42,457,119,898,856,22,39,113,913,464,692,311,70,80,984,502,325,636,697,668,364,629,101,248,696,40,912,222,185,55,889,992,602,655,412,799,974,624,896,190,855,778,171,262,771,953,350,283,71,264,351,762,68,828,898,599,447,144,199,134,520,677,753,580,827,310,82,876,392,44,70,695,429,678,882,215,243,116,893,887,423,366,718,926,229,400,924,899,810,523,141,134,101,165,378,314,959,477,965,836,260,800,584,315,950,595,752,538,250,615,183,280,935,849,831,723,762,837,347,857,135,259,981,115,228,814,338,542,945,899,91,876,982,588,856,937,776,583,9,102,494,807,146,174,479,516,675,427,727,761,46,940,209,613,148,563,7,143,513,938,805,656,258,521,877,851,720,813,610,756,994,911,626,24,125,453,824,103,197,239,389,682,927,6,113,122,307,545,354,128,912,744,469,145,603,20,506,106,298,382,451,216,285,577,157,264,262,473,87,953,381,669,495,840,160,348,261,218,600,168,119,895,262,301,565,121,308,974,913,658,682,895,935,30,95,692,277,320,952,401,341,619,201,194,904,986,258,994,903,280,147,439,312,414,535,107,72,399,892,403,947,816,716,919,396,467,418,855,362,610,435,205,110,918,464,386,531,295,37,652,661,498,330,608,389,585,96,543,443,582,739,179,258,580,405,127,836,313,65,57,898,766,559,879,907,910,434,140,909,487,438,546,250,872,33,549,111,258,903,751,336,239,666,972,512,702,953,822,948,370,387,14,59,35,561,350,250,912,920,585,84,169,592,625,715,349,106,569,174,583,582,419,50,78,862,168,319,880,847,849,513,851,565,943,187,608,902,352,97,717,293,535,107,321,391,372,254,628,246,944,647,848,493,570,301,451,602,445,544,862,276,827,779,507,299,533,652,794,68,732,959,756,203,422,469,296,649,322,194,918,610,383,356,208,482,501,922,544,786,147,729,872,962,598,224,183,850,475,377,777,325,46,746,591,77,37,977,189,548,745,255,140,5,133,615,809,596,706,842,742,193,217,761,211,694,949,26,550,307,483,34,507,849,290,679,179,41,117,305,103,863,918,263,291,792,624,851,41,684,332,255,528,364,616,511,316,701,546,296,671,59,160,326,819,523,196,139,699,207,853,344,757,643,744,612,55,867,984,997,551,818,336,121,875,20,243,416,163,353,692,227,987,479,82,321,660,203,643,910,551,400,171,347,77,168,626,512,14,709,526,144,660,321,903,863,119,242,83,698,259,515,303,457,479,550,365,607,56,574,158,507,746,504,649,696,638,276,305,555,765,283,124,948,485,285,447,66,870,760,127,100,964,969,925,785,93,98,764,386,260,609,451,521,151,386,313,328,398,553,603,518,919,224,50,265,626,691,385,941,654,508,847,476,446,624,504,526,324,985,97,515,191,863,359,484,538,465,495,734,600,601,610,858,646,970,754,847,573,443,332,534,688,586,879,863,721,23,985,970,72,365,397,631,379,762,986,647,206,956,542,92,288,60,635,538,973,211,619,105,740,895,186,872,329,518,444,117,619,273,722,852,484,70,840,891,204,205,911,313,134,677,661,232,918,541,747,860,2,241,798,435,978,408,516,587,36,395,889,16,348,606,93,368,961,516,27,980,851,578,105,234,196,230,823,926,133,235,722,770,681,703,999,204,657,916,790,394,705,923,530,352,650,316,394,228,709,841,709,454,13,416,154,349,354,450,99,278,537,817,907,255,19,84,916,907,803,400,178,688,972,583,178,118,335,781,465,271,963,633,408,837,515,407,521,715,978,437,264,897,679,482,788,208,676,960,694,233,101,349,715,408,87,127,881,255,246,29,750,570,327,258,826,173,218,379,581,808,408,83,290,729,6,41,1000,403,776,66,284,513,997,797,876,638,469,3,154,702,325,502,280,296,262,591,370,199,675,867,426,51,489,615,662,222,798,282,579,819,366,983,579,551,280,67,806,20,631,784,923,113,338,618,398,110,494,378,140,866,217,851,398,382,964,14,185,784,119,510,947,376,763,934,260,350,285,322,484,458,634,778,516,320,916,718,582,14,265,460,323,426,845,448,212,905,850,588,469,91,981,242,870,350,467,606,939,171,246,633,914,672,21,375,547,264,587,688,356,501,158,816,690,512,739,588,639,105,206,77,917,474,463,905,288,828,887,340,640,741,505,151,804,831,264,324,0,816,567,948,101,662,27,273,641,281,2,454,581,586,592,710,626,931,435,812,706,101,57,452,72,975,490,386,66,409,1,738,176,555,125,21,718,723,499,159,872,821,232,625,136,414,299,231,322,919,151,335,532,101,254,747,103,284,753,715,631,507,492,232,679,412,494,55,545,446,516,979,675,799,292,592,987,781,729,800,590,713,801,636,287,652,979,859,735,161,345,239,43,264,186,473,403,607,615,340,135,746,924,175,449,721,947,865,54,879,770,144,52,37,323,187,273,415,632,375,897,695,358,682,451,354,850,767,359,748,715,462,101,466,335,280,420,157,433,610,766,442,588,745,325,374,917,526,85,606,889,806,496,897,126,803,315,672,416,591,46,258,682,255,623,219,287,585,616,8,662,548,675,85,656,59,682,420,503,70,339,636,853,578,103,523,377,400,419,878,507,586,226,697,628,587,839,109,13,462,831,240,39,873,133,384,354,557,954,212,18,20,830,171,225,392,147,249,941,155,428,864,470,960,18,350,477,590,91,562,311,684,553,485,383,864,170,179,352,941,54,455,72,301,100,781,558,837,910,259,659,869,172,861,43,507,343,727,819,461,7,116,37,955,520,941,79,52,564,320,947,594,673,531,422,184,650,800,12,718,293,144,891,687,873,123,773,382,438,532,381,441,317,119,964,87,160,202,798,979,276,128,307,303,125,240,587,281,95,178,573,693,646,943,297,775,267,366,486,43,994,3,968,345,276,696,975,342,487,616,158,88,664,266,298,348,822,912,780,361,381,921,85,771,348,125,472,414,633,128,436,110,303,986,794,523,67,25,674,347,532,451,279,792,603,881,11,385,575,448,670,809,432,852,675,487,444,74,788,848,708,492,678,387,146,954,764,47,228,934,928,591,606,489,554,727,307,498,560,727,185,544,284,464,365,613,113,89,954,599,892,731,194,859,119,503,726,475,610,339,782,0,843,189,14,462,220,550,20,34,295,718,145,129,36,873,408,184,565,437,683,749,457,861,498,380,942,682,292,632,411,179,245,410,834,437,647,66,502,113,344,963,261,986,292,253,188,840,51,312,705,543,770,227,318,713,886,760,568,564,463,508,795,991,13,592,662,258,388,186,429,149,283,687,548,914,409,86,365,256,189,685,349,340,872,50,360,736,744,228,646,951,631,409,816,443,215,96,990,186,570,728,715,235,625,821,188,504,961,615,223,496,936,963,302,78,477,976,353,230,542,323,187,461,228,290,619,885,171,787,856,718,746,755,1000,439,897,419,370,404,503,897,698,390,907,224,278,53,549,658,247,480,778,56,395,934,289,618,711,880,427,93,95,121,783,17,174,113,414,716,464,375,837,791,350,964,683,814,439,688,388,137,724,170,487,493,66,608,40,543,114,590,53,82,887,628,276,707,930,879,753,105,626,208,35,610,147,52,553,242,715,791,147,917,497,967,442,264,153,805,663,557,158,892,25,237,163,77,188,311,386,486,428,41,920,350,849,182,730,671,290,362,885,384,698,350,818,554,620,900,130,426,607,654,371,770,847,410,318,987,946,109,15,837,586,614,191,569,370,98,919,912,417,818,447,1,10,653,512,249,580,505,273,893,533,814,729,158,878,152,147,970,125,791,438,509,677,729,555,102,431,828,150,674,344,712,989,5,854,204,339,594,171,532,412,40,442,482,229,264,270,473,203,843,644,684,185,717,280,174,49,258,420,220,983,390,349,684,350,717,672,366,35,747,925,677,102,200,695,471,63,828,72,202,72,229,686,184,747,613,716,691,55,186,7,333,770,976,676,864,917,901,736,772,551,425,800,323,169,549,604,70,385,361,631,33,341,241,369,434,680,359,441,309,867,942,847,625,610,797,96,160,246,188,905,819,927,122,789,348,932,633,723,63,248,745,207,433,341,76,126,478,384,905,253,497,103,960,336,158,822,565,105,892,433,927,20,509,459,254,213,615,500,153,549,581,889,356,960,122,26,711,336,830,950,591,228,992,94,680,754,560,806,17,115,948,743,97,291,817,201,361,697,928,578,1000,213,25,938,148,637,596,651,250,145,615,474,756,556,877,238,535,336,710,551,55,898,388,714,757,555,836,682,687,208,829,646,422,599,697,726,207,514,880,722,935,752,775,209,515,581,689,878,981,312,783,264,274,655,355,503,763,491,326,333,302,571,403,183,725,779,964,850,608,345,432,472,246,681,575,5,241,769,720,623,255,106,239,406,798,763,317,784,859,481,690,159,592,296,585,431,16,292,82,931,167,619,439,633,477,199,293,83,900,780,663,293,230,887,208,356,109,137,297,431,50,563,568,893,685,40,174,681,252,89,446,703,693,915,373,732,897,687,412,901,151,907,872,969,749,537,349,298,979,801,943,176,699,669,966,498,539,424,463,91,710,411,686,74,488,751,975,813,837,373,13,23,450,22,43,656,88,557,779,559,680,352,222,586,262,103,660,607,861,420,341,613,129,831,432,690,577,666,691,41,151,454,955,66,798,117,373,944,1,689,749,932,998,306,590,971,11,389,876,203,695,990,561,627,834,996,31,708,697,935,543,598,650,614,411,775,816,469,866,868,746,8,998,531,775,405,471,669,459,956,796,174,134,528,688,174,833,280,693,679,757,146,650,589,88,657,59,563,489,457,67,99,446,982,109,558,342,473,252,987,994,169,220,802,94,453,503,444,624,876,416,657,731,886,826,308,758,39,191,146,795,664,363,549,794,17,333,804,686,156,69,264,151,618,13,327,637,970,360,3,104,997,762,649,770,653,854,457,555,440,610,892,39,254,610,643,727,473,484,221,249,554,424,225,366,802,839,751,382,51,617,412,73,226,211,191,386,765,700,624,487,699,622,802,659,377,451,852,616,842,875,752,72,667,195,657,28,419,362,872,639,748,619,152,20,150,633,894,933,673,412,565,923,855,614,517,433,663,306,7,82,397,903,734,134,631,402,465,739,987,135,332,860,357,568,976,52,304,11,638,313,137,728,973,684,698,81,724,167,131,810,222,496,177,3,228,3,992,151,847,274,783,482,12,208,556,898,73,618,737,419,184,970,381,287,501,201,503,241,290,488,128,233,701,303,468,445,701,302,287,583,600,843,485,374,247,425,434,903,524,158,678,362,592,491,973,517,84,496,187,662,53,83,804,943,397,498,610,651,263,50,718,541,708,273,299,816,935,874,163,624,374,564,289,53,121,547,20,776,638,638,722,175,34,760,538,230,887,992,247,130,665,316,95,644,422,944,735,505,354,210,847,773,800,981,658,613,514,635,581,666,174,642,933,740,707,446,166,478,906,168,155,278,149,337,627,623,772,844,204,960,963,327,152,188,600,522,106,32,998,583,552,929,682,720,682,646,587,970,102,467,363,585,429,863,123,951,572,686,776,477,793,486,969,545,110,486,327,97,577,847,498,852,456,63,57,927,275,707,899,740,788,769,827,608,772,166,30,573,371,596,269,43,941,292,908,663,376,352,604,536,306,245,337,98,978,151,618,943,83,917,54,278,557,522,214,212,364,735,789,912,151,833,675,724,347,189,536,838,228,243,782,443,13,722,121,415,549,38,126,153,884,824,161,498,848,754,417,97,988,114,521,567,210,553,369,220,256,700,910,120,142,348,907,939,541,731,748,861,606,314,762,324,831,999,724,812,515,907,174,14,588,398,937,787,943,777,314,700,243,78,381,446,256,620,935,594,431,768,581,403,101,117,990,656,842,495,990,797,745,732,725,139,109,171,35,705,497,650,619,81,654,764,50,315,58,579,135,39,99,597,519,941,181,268,989,389,902,425,703,522,454,321,315,371,915,858,711,817,767,757,64,356,969,958,509,193,11,470,475,564,451,256,114,844,12,490,121,879,720,13,931,450,416,209,470,440,533,698,717,28,742,66,208,277,416,188,833,954,956,745,946,686,303,720,485,335,809,993,250,47,314,140,529,500,987,375,587,771,77,855,368,985,930,691,624,621,886,376,659,98,216,472,763,153,801,411,966,944,640,762,167,828,996,409,140,771,112,372,160,166,3,636,575,464,344,724,414,56,634,105,305,814,920,735,511,285,492,529,716,420,27,929,32,585,855,869,969,157,884,117,47,112,247,407,808,259,324,39,82,397,88,608,431,787,914,574,860,51,138,1000,285,337,741,401,437,259,515,765,563,194,838,984,760,414,340,950,4,694,234,947,222,432,911,97,238,678,831,491,813,48,977,703,569,162,791,212,748,272,303,834,453,661,784,88,801,197,648,857,684,711,982,358,589,789,318,773,898,651,328,317,138,157,327,720,26,692,462,639,65,32,130,471,266,15,340,530,731,22,893,767,627,151,501,671,141,311,942,4,844,739,948,417,621,160,858,50,633,972,228,572,103,120,592,859,225,605,254,683,927,427,193,748,65,90,574,952,658,796,839,471,423,436,907,666,335,952,666,717,536,116,131,437,473,688,121,765,685,976,414,478,680,493,949,209,742,507,585,913,971,43,232,607,422,774,596,435,303,911,386,934,4,899,749,301,279,95,543,353,575,109,82,362,140,645,439,999,240,320,694,30,419,180,132,80,606,592,653,468,581,116,79,177,708,232,995,587,53,236,144,804,698,329,773,776,689,702,831,461,599,571,682,1000,656,348,921,546,800,745,389,717,530,262,248,724,598,37,178,271,884,436,405,949,63,605,963,822,498,72,928,499,192,683,235,580,694,65,700,836,278,377,525,667,110,239,671,273,496,696,979,648,402,286,943,735,620,292,424,148,820,450,402,378,206,171,150,356,728,414,677,557,62,136,187,742,841,258,819,559,340,908,985,262,102,82,759,386,907,378,997,520,311,503,429,315,632,140,93,802,153,608,709,824,310,585,525,949,663,268,839,426,240,177,70,410,123,899,290,0,286,660,880,116,913,698,878,735,73,724,101,466,519,844,559,466,348,295,275,506,435,371,67,858,502,399,27,944,180,302,412,554,430,505,269,211,390,341,379,750,874,526,33,320,699,404,462,264,96,877,351,959,821,704,577,932,49,64,777,107,947,188,401,715,966,264,561,76,141,89,971,74,405,358,63,929,550,998,556,202,57,35,345,996,271,207,111,738,769,475,949,854,61,725,660,80,594,32,752,824,183,79,219,655,966,126,666,654,376,958,78,685,886,700,638,659,702,270,231,825,425,272,534,712,580,422,667,68,942,990,433,731,6,560,539,312,799,559,47,656,264,804,762,666,501,320,147,628,420,906,193,760,587,133,771,611,197,165,542,730,500,959,591,729,856,302,653,393,991,150,735,215,184,18,95,272,946,330,719,653,937,147,133,312,501,414,62,238,217,727,926,824,876,920,741,513,342,18,783,628,602,438,735,87,345,217,774,390,952,461,559,259,662,820,530,934,836,545,896,269,553,754,672,252,78,860,539,171,916,48,283,325,129,248,509,945,965,425,395,158,968,420,166,250,242,431,878,784,753,12,115,571,245,876,831,134,677,855,606,562,567,713,551,962,526,257,633,420,195,678,564,328,491,31,916,197,183,536,782,19,490,222,845,162,162,456,607,690,713,294,214,517,912,299,126,492,808,467,519,430,48,415,165,336,241,422,707,236,434,718,745,328,228,873,619,301,572,325,598,170,124,128,780,754,638,280,16,302,198,452,876,797,603,851,314,596,960,705,876,661,915,116,279,573,306,144,145,473,334,128,66,272,220,449,147,84,945,987,106,299,878,335,648,498,271,240,202,271,64,893,704,461,705,590,675,52,265,654,818,437,515,655,6,649,594,196,872,130,618,448,595,886,950,435,113,413,317,583,787,928,872,416,948,308,963,519,318,340,730,597,242,954,321,158,738,622,489,351,976,232,311,369,554,155,561,249,529,360,856,989,746,532,263,715,98,882,539,731,476,487,759,297,778,86,892,985,417,771,244,604,901,711,672,564,979,119,820,277,863,427,375,18,595,283,840,534,417,223,618,576,308,266,633,977,615,497,235,996,962,426,117,589,617,252,861,245,744,670,196,935,702,764,204,576,775,105,205,495,754,789,40,585,758,778,606,827,324,364,647,837,137,185,527,654,852,396,557,558,706,239,129,15,305,483,636,244,155,355,754,859,522,551,547,226,463,249,179,397,336,736,835,765,759,567,904,621,426,220,307,263,947,388,889,60,468,920,899,986,321,209,574,163,471,973,833,166,615,574,851,104,879,340,83,275,355,334,733,894,16,990,439,20,975,868,89,291,980,349,841,134,875,686,900,503,348,928,570,627,890,523,444,737,665,84,729,19,720,627,507,964,982,840,671,16,563,355,904,145,78,477,777,660,373,926,667,621,810,931,361,3,161,587,940,406,200,563,829,437,835,302,780,467,8,247,360,225,492,799,107,40,826,374,110,204,128,983,700,997,237,284,886,309,33,703,367,96,826,321,97,802,466,725,128,453,568,960,573,716,272,946,155,416,246,845,304,114,414,560,73,928,940,280,630,801,561,195,731,448,306,462,578,926,156,473,428,566,387,79,755,192,752,2,253,49,264,557,422,136,124,282,977,496,153,705,520,67,693,796,452,645,832,560,792,32,381,804,46,583,650,455,847,311,15,194,420,608,721,269,619,77,142,354,72,249,799,502,15,98,71,789,846,422,530,118,345,853,728,113,916,111,615,767,404,417,274,247,952,43,606,247,673,954,718,579,568,495,452,466,861,158,140,489,325,235,764,597,698,613,925,858,954,14,473,715,823,521,815,601,811,815,136,516,422,486,121,667,536,444,917,160,37,998,339,191,131,438,752,134,839,625,789,155,500,493,741,514,33,662,798,437,105,243,998,66,524,661,292,206,265,360,104,229,324,824,373,955,629,614,813,526,786,825,594,621,509,140,498,761,446,469,670,211,151,336,60,344,0,932,205,412,621,872,310,21,765,235,268];